package 剑指Offer._3140;

import general_class.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/26 16:27
 * 二叉树中和为某一值得路径
 * 算法：树  前序遍历
 * 遍历到叶子节点得时候判断以下
 * 当没到叶子节点时，当前值就比
 */
public class _34 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(-2, null, new TreeNode(-3, null, null));
        System.out.println(new _34().pathSum(root, -5));
    }

    int target;
    List<Integer> tmp;
    List<List<Integer>> ans;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        ans = new ArrayList<>();
        tmp = new ArrayList<>();
        this.target = target;
        if (root != null) dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode node, int cur) {
        if (node.left == null && node.right == null) {
            if (cur + node.val == target) {
                tmp.add(node.val);
                ans.add(new ArrayList<>(tmp));
                tmp.remove(tmp.size() - 1);
            }
            return;
        }
        tmp.add(node.val);
        if (node.left != null) dfs(node.left, cur + node.val);
        if (node.right != null) dfs(node.right, cur + node.val);
        tmp.remove(tmp.size() - 1);
    }

}
